home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d1 / coppy33.arc / SORT.C < prev   
C/C++ Source or Header  |  1989-02-17  |  4KB  |  165 lines
  1. /*                                  QSORT.C
  2.  *                                  =======
  3.  *   Quit sort routine from Dr. Dobb's Journal #102 April 1985.
  4.  */
  5.  
  6. #define   STAND      0
  7. #include <stdio.h>
  8.  
  9. #if STAND
  10. #define MAX_PTRS       500
  11. static char *pp[ MAX_PTRS ];
  12. static int   Lev = 0;               /* Recusion level */
  13. static int   Maxlev = 0;            /* Maximum */
  14. #endif
  15.  
  16. typedef int (* PFI)();              /* Pointer to a function that */
  17.                                     /* returns an int. */
  18. static  PFI    Comp;                /* Pointer to comparsion routine */
  19. static  int    Width;               /* Width of an object in bytes */
  20. /* ------------------------------------------------------------------ */
  21. sort(base,cnt)
  22. char *base;
  23. int cnt;
  24. {
  25.    qsort(base,cnt,sizeof(PFI),0);
  26.    return(0);
  27. }
  28.  
  29. /* ------------------------------------------------------------------ */
  30. int argvcmp( slp, s2p )
  31. char **slp,
  32.      **s2p;
  33. /* Comparsion routine for sorting an argv like list of pointers
  34.  * to strings. Just remove one level of indirection and call strcmp
  35.  * to do the comparsion.
  36.  */
  37. {
  38.   return( strcmp( *slp, *s2p ) * -1);
  39. }
  40. qsort( base, nel, width, compare )
  41. char *base;
  42. int   nel,
  43.       width,
  44.       (*compare)();
  45. /* Perform a quick sort on an array starting at base.
  46.  */
  47. {
  48.  
  49.   Width = width;
  50.   Comp = ( compare == (PFI)0 ) ? &argvcmp : compare ;
  51.  
  52.   if ( nel > 1 )
  53.     rqsort( base, base + ( ( nel - 1 ) * width ) );
  54.  
  55. #if STAND
  56.    ptext( nel, base );
  57. #endif
  58.  
  59. }
  60.  
  61. /* ------------------------------------------------------------------ */
  62.  
  63. static  rqsort( low, high )
  64. register char *low,
  65.               *high;
  66. /* Workhorse function called by the access routine, qsort().
  67.  */
  68. {  char *pivot,
  69.         *base;
  70.    static char *a,         /* Used for exchange, will not be needed */
  71.                *b;         /* during recusion, so they can be static.*/
  72.    static int   tmp,       /* That way they will not take up stack   */
  73.                 i;         /* space.                                 */
  74.  
  75.    base = low ;            /* Remember base address of array. */
  76.    pivot = high ;          /* Partition off the pivot.        */
  77.    high -= Width;
  78.  
  79.    do
  80.    {  while ( low < high  &&  (*Comp)(low,  pivot) <= 0 )
  81.         low  += Width;
  82.       while ( low < high  &&  (*Comp)(high, pivot) >= 0 )
  83.         high -= Width;
  84.  
  85.       if ( low < high )      /* Exchange low & high */
  86.       {
  87. /*
  88.          printf( "lev = %d: exchangeing high: <%s> & low <%s>\n",
  89.                       Lev, *((char **)high), *((char **)low));
  90. */
  91.          for ( b = low, a = high, i = Width; --i >= 0; a++, b++ )
  92.          {  tmp = *b;           /* Exchange *low and *high */
  93.             *b  = *a;
  94.             *a  = tmp;
  95.          }
  96.       }
  97.    } while ( low < high );
  98.  
  99.    if ( low < pivot  &&  (*Comp)(low,  pivot) > 0 )
  100.       for ( b = low, a = pivot, i = Width; --i >= 0; a++, b++ )
  101.       {  tmp = *b;           /* Exchange *low and *pivot */
  102.          *b  = *a;
  103.          *a  = tmp;
  104.       }
  105.  
  106.    low += Width;
  107.  
  108.    if ( high - base < pivot - low )
  109.    {
  110.       if ( low  < pivot )
  111.         rqsort( low,  pivot );
  112.       if ( base < high  )
  113.         rqsort( base, high );
  114.    }
  115.    else
  116.    {
  117.       if ( base < high  )
  118.         rqsort( base, high );
  119.       if ( low  < pivot )
  120.         rqsort( low,  pivot );
  121.    }
  122. }
  123.  
  124. /* ------------------------------------------------------------------ */
  125.  
  126. #if STAND
  127. static ptext( argc, argv )
  128. int    argc;
  129. char **argv;
  130. /* Print out argv, one element per line */
  131. {  register int i;
  132.  
  133.    for ( i = 1; --argc >= 0; i++ )
  134.      printf( "%s\n", *argv++ );
  135. }
  136.  
  137. main( argc, argv )
  138. int    argc;
  139. char **argv;
  140. {  char *malloc(),
  141.         *wk;
  142.  
  143.    if ( argc > 1 )
  144.      qsort( ++argv, --argc, sizeof(PFI), 0 );
  145.    else
  146.      {  argc = 0;
  147.         while ( 1 )
  148.         {  if ( ( wk = malloc( 80 ) ) == 0 )
  149.             { printf( "\nUnable to Malloc\n" );
  150.               exit( 0 );
  151.             }
  152.            if ( gets( wk ) == NULL )
  153.               break;
  154.            pp[ argc++ ] = wk ;
  155.            if ( argc > MAX_PTRS )
  156.             { printf( "\nToo many items for QSORT\n" );
  157.               exit( 0 );
  158.             }
  159.         }
  160.         printf("\r\n" );
  161.         qsort( pp, argc, sizeof(PFI), 0 );
  162.      }
  163. }
  164. #endif
  165.